package com.kingner.utils;

import java.util.*;

public class ACUtil {
//    内部类，用作AC前缀树节点
    public static class ACNode{
        // child存放子节点
        private HashMap<Character,ACNode> child;
        // 如果当前节点是敏感词结尾，返回敏感词长度 (在源文本中可通过长度回推出敏感词本身)
        private int endLen;
        // 失败指针
        private ACNode fail;

        public ACNode(){
            child = new HashMap<>();
            endLen = 0;
            fail = null;
        }
    }
//    内部类，用于存储匹配词返回结果
    public static class ResultNode{
        // 敏感词长度
        int len;
        // 敏感词结束位置
        int end;
        public ResultNode(int len,int end){
            this.len=len;
            this.end=end;
        }
    }

    // 在类初始化时，创建根结点
    private static ACNode root;
    public ACUtil(){
        root = new ACNode();
    }

    // 添加新词
    public static void insert(String s){
        char[] chars = s.toCharArray();
        // curNode 指向当前节点
        ACNode curNode = root;
        for(int i=0; i<chars.length;i++){
            //  未在子结点中获取到该字符的节点，则在创建新的节点
            if(curNode.child.get(chars[i]) == null)
                curNode.child.put(chars[i],new ACNode());
            //  当前节点指针后移
            curNode = curNode.child.get(chars[i]);
        }
        //  当前节点可作为结束节点
        curNode.endLen = s.length();
    }

    //  构建fail指针
    public static void buildFailPoint(){
        // 使用队列广度优先给每一层的节点设置fail节点
        Queue<ACNode> queue = new LinkedList<>();
        queue.add(root);

        // cur:当前节点， node:当前节点的子节点， fail:用于回推失败节点
        ACNode cur=null, node=null, fail=null;

        while (!queue.isEmpty()){
            cur = queue.poll();
            fail = cur.fail;
            //  遍历map集合（所有子节点）
            for(Map.Entry<Character, ACNode> c : cur.child.entrySet()){
                //  获取子节点，并初始化子节点的fail节点为root
                node = cur.child.get(c.getKey());
                node.fail = root;
                //  循环遍历回推失败节点
                while (fail!=null) {
                    if(fail.child.get(c.getKey())!=null){
                        node.fail=fail.child.get(c.getKey());
                        break;
                    }
                    else
                        fail=fail.fail;
                }
                queue.add(node);
            }
        }
    }

    //  查找文本敏感词，并以链表返回敏感词集合。
    public static List<String> search(String s){
        List<String> res = new ArrayList<>();
        ACNode cur = root, fail;
        char c;
        // 遍历文本
        for(int i=0;i<s.length();i++){
            c = s.charAt(i);
            while (cur!=root && cur.child.get(c)==null){
                cur = cur.fail;
            }

            if(cur.child.get(c)!=null){
                cur = cur.child.get(c);
                if(cur.endLen!=0)
                    res.add(s.substring(i-cur.endLen+1,i+1));
            }
        }
        return res;
    }

    //  返回每个敏感词的位置和长度
    public static List<ResultNode> searchNode(String s){
        List<ResultNode> res = new ArrayList<>();
        ACNode cur = root, fail;
        char c;
        // 遍历文本
        for(int i=0;i<s.length();i++){
            c = s.charAt(i);
            while (cur!=root && cur.child.get(c)==null){
                cur = cur.fail;
            }

            if(cur.child.get(c)!=null){
                cur = cur.child.get(c);
                if(cur.endLen!=0)
                    res.add(new ResultNode(cur.endLen,i+1));
            }
        }
        return res;
    }

    // 将所有铭感词用*替换
    public static String replace(String text){
        StringBuffer sb = new StringBuffer(text);
        List<ResultNode> rn = searchNode(text);
        for(ResultNode r : rn){
            sb.replace(r.end-r.len,r.end,makeStar(r.len));
        }
        return sb.toString();
    }

    // 生成给定长度的*
    public static String makeStar(int n){
        StringBuffer sb = new StringBuffer();
        for(int i=0;i<n;i++){
            sb.append("*");
        }
        return sb.toString();
    }
}
